class Solution
{
public:
    int mincostTickets(vector<int> &days, vector<int> &costs)
    {
        vector<int> dp(366, 0);
        int tourDay = 0;
        for (int day = 1; day <= 365; ++day)
        {
            if (day != days[tourDay])
            {
                dp[day] = dp[day - 1];
                continue;
            }

            int minCost = dp[day - 1] + costs[0];
            for (int prevDay = max(day - 7, 0); prevDay < day; ++prevDay)
            {
                minCost = min(minCost, dp[prevDay] + costs[1]);
            }
            for (int prevDay = max(day - 30, 0); prevDay < day; ++prevDay)
            {
                minCost = min(minCost, dp[prevDay] + costs[2]);
            }
            dp[day] = minCost;

            ++tourDay;
            if (tourDay == days.size())
            {
                return dp[day];
            }
        }
        return dp[365];
    }
};